Implement P0253R1: Fixing a design mistake in the searchers interface. git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@262928 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/algorithm b/include/algorithm index 7dba11e..f439396 100644 --- a/include/algorithm +++ b/include/algorithm
@@ -1421,20 +1421,20 @@ // search template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> -_ForwardIterator1 +pair<_ForwardIterator1, _ForwardIterator1> __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { if (__first2 == __last2) - return __first1; // Everything matches an empty sequence + return make_pair(__first1, __first1); // Everything matches an empty sequence while (true) { // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks while (true) { if (__first1 == __last1) // return __last1 if no element matches *__first2 - return __last1; + return make_pair(__last1, __last1); if (__pred(*__first1, *__first2)) break; ++__first1; @@ -1445,9 +1445,9 @@ while (true) { if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) - return __first1; + return make_pair(__first1, __m1); if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found - return __last1; + return make_pair(__last1, __last1); if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 { ++__first1; @@ -1458,20 +1458,21 @@ } template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 +_LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_RandomAccessIterator1, _RandomAccessIterator1> __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { - typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _D2; + typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; + typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - _D2 __len2 = __last2 - __first2; + const _D2 __len2 = __last2 - __first2; if (__len2 == 0) - return __first1; - _D1 __len1 = __last1 - __first1; + return make_pair(__first1, __first1); + const _D1 __len1 = __last1 - __first1; if (__len1 < __len2) - return __last1; + return make_pair(__last1, __last1); const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here while (true) { @@ -1479,7 +1480,7 @@ while (true) { if (__first1 == __s) - return __last1; + return make_pair(__last1, __last1); if (__pred(*__first1, *__first2)) break; ++__first1; @@ -1511,7 +1512,7 @@ if (__pred(*__first1, *__first2)) break; case 0: - return __last1; + return make_pair(__last1, __last1); } __phase2: #endif // !_LIBCPP_UNROLL_LOOPS @@ -1521,7 +1522,7 @@ while (true) { if (++__m2 == __last2) - return __first1; + return make_pair(__first1, __first1 + __len2); ++__m1; // no need to check range on __m1 because __s guarantees we have enough source if (!__pred(*__m1, *__m2)) { @@ -1561,7 +1562,7 @@ if (!__pred(*__m1, *__m2)) break; case 0: - return __first1; + return make_pair(__first1, __first1 + __len2); } __continue: ++__first1; @@ -1577,8 +1578,9 @@ { return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type> (__first1, __last1, __first2, __last2, __pred, - typename std::iterator_traits<_ForwardIterator1>::iterator_category(), - typename std::iterator_traits<_ForwardIterator2>::iterator_category()); + typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()) + .first; } template <class _ForwardIterator1, class _ForwardIterator2> @@ -1587,8 +1589,8 @@ search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename std::iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename std::iterator_traits<_ForwardIterator2>::value_type __v2; + typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; + typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } diff --git a/include/experimental/algorithm b/include/experimental/algorithm index ffaa793..3902111 100644 --- a/include/experimental/algorithm +++ b/include/experimental/algorithm
@@ -53,7 +53,7 @@ template <class _ForwardIterator, class _Searcher> _LIBCPP_INLINE_VISIBILITY _ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) -{ return __s(__f, __l); } +{ return __s(__f, __l).first; } template <class _PopulationIterator, class _SampleIterator, class _Distance, diff --git a/include/experimental/functional b/include/experimental/functional index c7a7869..75fc8e9 100644 --- a/include/experimental/functional +++ b/include/experimental/functional
@@ -119,9 +119,12 @@ template <typename _ForwardIterator2> _LIBCPP_INLINE_VISIBILITY - _ForwardIterator2 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const + pair<_ForwardIterator2, _ForwardIterator2> + operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - return _VSTD::search(__f, __l, __first_, __last_, __pred_); + return _VSTD::__search(__f, __l, __first_, __last_, __pred_, + typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category(), + typename _VSTD::iterator_traits<_ForwardIterator2>::iterator_category()); } private: @@ -233,7 +236,7 @@ } template <typename _RandomAccessIterator2> - _RandomAccessIterator2 + pair<_RandomAccessIterator2, _RandomAccessIterator2> operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const { static_assert ( std::is_same< @@ -242,12 +245,12 @@ >::value, "Corpus and Pattern iterators must point to the same type" ); - if (__f == __l ) return __l; // empty corpus - if (__first_ == __last_) return __f; // empty pattern + if (__f == __l ) return make_pair(__l, __l); // empty corpus + if (__first_ == __last_) return make_pair(__f, __f); // empty pattern // If the pattern is larger than the corpus, we can't find it! if ( __pattern_length_ > _VSTD::distance (__f, __l)) - return __l; + return make_pair(__l, __l); // Do the search return this->__search(__f, __l); @@ -262,7 +265,8 @@ shared_ptr<vector<difference_type>> __suffix_; template <typename _RandomAccessIterator2> - _RandomAccessIterator2 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const + pair<_RandomAccessIterator2, _RandomAccessIterator2> + __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const { _RandomAccessIterator2 __cur = __f; const _RandomAccessIterator2 __last = __l - __pattern_length_; @@ -278,7 +282,7 @@ __j--; // We matched - we're done! if ( __j == 0 ) - return __cur; + return make_pair(__cur, __cur + __pattern_length_); } // Since we didn't match, figure out how far to skip forward @@ -290,7 +294,7 @@ __cur += __suffix[ __j ]; } - return __l; // We didn't find anything + return make_pair(__l, __l); // We didn't find anything } @@ -384,8 +388,8 @@ } } - template <typename _RandomAccessIterator2> - _RandomAccessIterator2 + template <typename _RandomAccessIterator2> + pair<_RandomAccessIterator2, _RandomAccessIterator2> operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const { static_assert ( std::is_same< @@ -394,12 +398,12 @@ >::value, "Corpus and Pattern iterators must point to the same type" ); - if (__f == __l ) return __l; // empty corpus - if (__first_ == __last_) return __f; // empty pattern + if (__f == __l ) return make_pair(__l, __l); // empty corpus + if (__first_ == __last_) return make_pair(__f, __f); // empty pattern // If the pattern is larger than the corpus, we can't find it! if ( __pattern_length_ > _VSTD::distance (__f, __l)) - return __l; + return make_pair(__l, __l); // Do the search return this->__search(__f, __l); @@ -413,7 +417,8 @@ shared_ptr<skip_table_type> __skip_; template <typename _RandomAccessIterator2> - _RandomAccessIterator2 __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const { + pair<_RandomAccessIterator2, _RandomAccessIterator2> + __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const { _RandomAccessIterator2 __cur = __f; const _RandomAccessIterator2 __last = __l - __pattern_length_; const skip_table_type & __skip = *__skip_.get(); @@ -427,12 +432,12 @@ __j--; // We matched - we're done! if ( __j == 0 ) - return __cur; + return make_pair(__cur, __cur + __pattern_length_); } __cur += __skip[__cur[__pattern_length_-1]]; } - return __l; + return make_pair(__l, __l); } }; diff --git a/include/string b/include/string index 9150244..004dc3d 100644 --- a/include/string +++ b/include/string
@@ -982,7 +982,7 @@ const _CharT* __r = _VSTD::__search(__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq, - random_access_iterator_tag(), random_access_iterator_tag()); + random_access_iterator_tag(), random_access_iterator_tag()).first; if (__r == __p + __sz) return __npos; return static_cast<_SizeT>(__r - __p);
diff --git a/test/std/experimental/algorithms/alg.search/search.pass.cpp b/test/std/experimental/algorithms/alg.search/search.pass.cpp index 60a44e4..579c13d 100644 --- a/test/std/experimental/algorithms/alg.search/search.pass.cpp +++ b/test/std/experimental/algorithms/alg.search/search.pass.cpp
@@ -15,7 +15,7 @@ // ForwardIterator search(ForwardIterator first, ForwardIterator last, // const Searcher& searcher); // -// returns searcher.operator(first, last) +// returns searcher.operator(first, last).first // #include <experimental/algorithm> @@ -27,10 +27,11 @@ struct MySearcher { template <typename Iterator> - Iterator operator() ( Iterator b, Iterator /*e*/) const + std::pair<Iterator, Iterator> + operator() (Iterator b, Iterator e) const { ++searcher_called; - return b; + return std::make_pair(b, e); } }; diff --git a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/default.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/default.pass.cpp index 7647b53..4ef70c7 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/default.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/default.pass.cpp
@@ -21,7 +21,7 @@ // Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); // // template<class RandomAccessIterator2> -// RandomAccessIterator2 +// pair<RandomAccessIterator2, RandomAccessIterator2> // operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; // // private:
diff --git a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pass.cpp index 1323044..1162ef6 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pass.cpp
@@ -21,7 +21,7 @@ // Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); // // template<class RandomAccessIterator2> -// RandomAccessIterator2 +// pair<RandomAccessIterator2, RandomAccessIterator2> // operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; // // private:
diff --git a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pred.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pred.pass.cpp index 8fd5b8c..629a038 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pred.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pred.pass.cpp
@@ -21,7 +21,7 @@ // Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); // // template<class RandomAccessIterator2> -// RandomAccessIterator2 +// pair<RandomAccessIterator2, RandomAccessIterator2> // operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; // // private:
diff --git a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/pred.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/pred.pass.cpp index d0655c8..9d29cb6 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/pred.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/pred.pass.cpp
@@ -21,7 +21,7 @@ // Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); // // template<class RandomAccessIterator2> -// RandomAccessIterator2 +// pair<RandomAccessIterator2, RandomAccessIterator2> // operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; // // private:
diff --git a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/default.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/default.pass.cpp index af3bbba..e4d1883 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/default.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/default.pass.cpp
@@ -21,7 +21,7 @@ // Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); // // template<class RandomAccessIterator2> -// RandomAccessIterator2 +// pair<RandomAccessIterator2, RandomAccessIterator2> // operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; // // private:
diff --git a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pass.cpp index ff289f0..be116ec 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pass.cpp
@@ -21,7 +21,7 @@ // Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); // // template<class RandomAccessIterator2> -// RandomAccessIterator2 +// pair<RandomAccessIterator2, RandomAccessIterator2> // operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; // // private:
diff --git a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp index 1150210..d63acf0 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp
@@ -21,7 +21,7 @@ // Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); // // template<class RandomAccessIterator2> -// RandomAccessIterator2 +// pair<RandomAccessIterator2, RandomAccessIterator2> // operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; // // private:
diff --git a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/pred.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/pred.pass.cpp index 5542687..3cd41c7 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/pred.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/pred.pass.cpp
@@ -21,7 +21,7 @@ // Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); // // template<class RandomAccessIterator2> -// RandomAccessIterator2 +// pair<RandomAccessIterator2, RandomAccessIterator2> // operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; // // private:
diff --git a/test/std/experimental/func/func.searchers/func.searchers.default/default.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.default/default.pass.cpp index 446dcbd..a2dbceb 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.default/default.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.default/default.pass.cpp
@@ -20,7 +20,8 @@ // : __first_(__f), __last_(__l), __pred_(__p) {} // // template <typename _ForwardIterator2> -// _ForwardIterator2 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { +// pair<_ForwardIterator2, _ForwardIterator2> +// operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { // return std::search(__f, __l, __first_, __last_, __pred_); // } // diff --git a/test/std/experimental/func/func.searchers/func.searchers.default/default.pred.pass.cpp b/test/std/experimental/func/func.searchers/func.searchers.default/default.pred.pass.cpp index b65c500..e951b46 100644 --- a/test/std/experimental/func/func.searchers/func.searchers.default/default.pred.pass.cpp +++ b/test/std/experimental/func/func.searchers/func.searchers.default/default.pred.pass.cpp
@@ -20,7 +20,8 @@ // : __first_(__f), __last_(__l), __pred_(__p) {} // // template <typename _ForwardIterator2> -// _ForwardIterator2 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { +// pair<_ForwardIterator2, _ForwardIterator2> +// operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { // return std::search(__f, __l, __first_, __last_, __pred_); // } // diff --git a/www/cxx1z_status.html b/www/cxx1z_status.html index 2c69bec..80097fe 100644 --- a/www/cxx1z_status.html +++ b/www/cxx1z_status.html
@@ -86,7 +86,7 @@ <tr><td><a href="http://wg21.link/P0005R4">P0005R4</a></td><td>LWG</td><td>Adopt not_fn from Library Fundamentals 2 for C++17</td><td>Jacksonville</td><td></td><td></td></tr> <tr><td><a href="http://wg21.link/P0152R1">P0152R1</a></td><td>LWG</td><td>constexpr atomic::is_always_lock_free</td><td>Jacksonville</td><td></td><td></td></tr> <tr><td><a href="http://wg21.link/P0185R1">P0185R1</a></td><td>LWG</td><td>Adding [nothrow-]swappable traits</td><td>Jacksonville</td><td></td><td></td></tr> - <tr><td><a href="http://wg21.link/P0253R1">P0253R1</a></td><td>LWG</td><td>Fixing a design mistake in the searchers interface</td><td>Jacksonville</td><td></td><td></td></tr> + <tr><td><a href="http://wg21.link/P0253R1">P0253R1</a></td><td>LWG</td><td>Fixing a design mistake in the searchers interface</td><td>Jacksonville</td><td>Complete</td><td>3.9</td></tr> <tr><td><a href="http://wg21.link/P0025R0">P0025R0</a></td><td>LWG</td><td>An algorithm to "clamp" a value between a pair of boundary values</td><td>Jacksonville</td><td>Complete</td><td>3.9</td></tr> <tr><td><a href="http://wg21.link/P0154R1">P0154R1</a></td><td>LWG</td><td>constexpr std::hardware_{constructive,destructive}_interference_size</td><td>Jacksonville</td><td></td><td></td></tr> <tr><td><a href="http://wg21.link/P0030R1">P0030R1</a></td><td>LWG</td><td>Proposal to Introduce a 3-Argument Overload to std::hypot</td><td>Jacksonville</td><td></td><td></td></tr> 